# 3. DFT, DFS, FFT 总结
## 3.1 信号与空间
**向量集合 $\mathbb V$**：可以定义加法、标量乘法、满足交换律、结合律、分配律、存在加法零元、加法逆元、乘法单位元。
**向量的内积** 定义为：
$$
\left\langle\cdot,\cdot \right\rangle: \ \mathbb V \times \mathbb V \to \mathbb F
$$
内积用于测量向量间的相似性。如果内积为零，则称向量是正交的。
内积满足的特性：分配性、共轭对称性、标度性、正定性、正交性。
- $\R^n$ 空间中的内积：$\displaystyle \sum_{n=0}^{N-1} x_ny_n$.
- $\C^N$ 空间中的内积：$\displaystyle \sum_{n=0}^{N-1} x_n^*y_n$.
- $L_2([-1,1])$ 空间中的内积：$\displaystyle \int_{-1}^{1} x(t)y(t)\mathrm d t$.
**信号空间** 有限支持序列和周期性序列可以定义在 $\C^N$ 空间中：
$$
\bold x=[x_0, x_1,\cdots,x_{N-1}]^\top
$$
- 有限支持序列的内积：$\displaystyle \left\langle\bold x,\bold y\right\rangle=\displaystyle \sum_{n=0}^{N-1} x_n^*y_n$
- 无限长度序列的内积：$\displaystyle \left\langle\bold x,\bold y\right\rangle=\displaystyle \sum_{n=-\infin}^{\infin} x_n^*y_n$
要求序列是平方可加的。
**基向量** 在向量空间 $\mathbb H$，找到一个向量集合 $\{\bold w^{(k)}\}$，包含最少的向量数，使得其他任意向量空间中的向量都可以写成这些向量的线性组合。
也就是满足以下条件，
$$
\bold x=\sum_{k=0}^{K-1} \alpha_k \bold w^{(k)},\quad \alpha_k\in \C
$$
使得基系数 $\alpha_k$ 是唯一的。并且基向量之间线性无关。
- 正交基向量的性质：$\left\langle \bold w^{(k)},\bold w^{(n)}\right\rangle=0$ 当 $k\not= n$.
- 归一化正交基向量的性质：$\left\langle \bold w^{(k)},\bold w^{(n)}\right\rangle=\delta[n-k]$.
当基向量归一化的时候，基系数计算简单，
$$
\alpha_k=\left\langle\bold w^{(k)},\bold x\right\rangle
$$
但是当正交基未归一化时，不能直接使用这个方法计算。
例如，$[-1,1]$ 区间的傅里叶基函数：
$$
\frac{1}{\sqrt{2}},\cos \pi t,\sin \pi t,\cos 2\pi t,\sin 2\pi t,\cdots
$$
利用傅里叶基函数可以近似非连续函数，例如 $h(t)=\operatorname{sgn}(t)$，使用：
$$
\hat h(t)=\sum_{k=0}^{N} \frac{1}{2k+1} \sin[(2k+1)\pi t]
$$
近似。近似的结果满足均方收敛的条件，但是非一致收敛。
## 3.2 DFT
**DFT 在信号空间中的表征** 由时域基转换到了频域基：
$$
[\bold w^{(k)}]_{n}=e^{j\frac{2\pi}{N}kn}
$$
可以证明是正交的，但是没有进行归一化. DFT 矩阵：
$$
\bold W_{N}=[\bold w^{(0)},\cdots,\bold w^{(n-1)}]^H
$$
DFT 公式：
$$
[\bold X]_k=\left\langle \bold w^{(k)},\bold x\right\rangle\Rightarrow \bold X=\bold W_N\bold x
$$
IDFT 公式：
$$
\bold x=\frac{1}{N}\bold W_N^H \bold X
$$
**DFT 公式和 IDFT 公式**
$$
\boxed{X[k]=\sum_{n=0}^{N-1}x[n]e^{-j\frac{2\pi}{N}kn},\quad k=0,1,\cdots,N-1}\\
\boxed{x[n]=\frac{1}{N}\sum_{k=0}^{N-1} X[k] e^{j\frac{2\pi}{N}kn},\quad n=0,1,\cdots,N-1}
$$
**DFT 示例：余弦序列**
当相位为零，
$$
x[n]=3\cos\left(\frac{2\pi \cdot 4n}{64}\right),\quad x[n]\in \C^{64}
$$
$$
\omega=\frac{2\pi\cdot k}{N}
$$
$$
x[n]=\frac{3}{2}(w_4[n]+w_{60}[n])
$$
$$
X[k]=\left\langle w_k[n],x[n]\right\rangle=96(\delta[k-4]+\delta[k-60])
$$
注意，$w_k[n]$ 未进行归一化。
当相位不为零，
$$
x[n]=3\cos\left(\frac{2\pi \cdot 4n}{64}+\frac{\pi}{3}\right),\quad x[n]\in \C^{64}
$$
$$
x[n]=\frac{3}{2}(e^{j\pi/3}w_4[n]+e^{-j\pi/3}w_{60}[n])
$$
$$
X[k]=\left\langle w_k[n],x[n]\right\rangle=96 e^{j\pi/3}\delta[k-4]+96e^{-j\pi/3}\delta[k-60]
$$
幅值不变，相角发生了变化。
**DFT 示例：矩形窗信号** $M$ 宽 $N$ 长的矩形信号。
$$
X[k]=\frac{\sin \left(\frac{\pi}{N}Mk\right)}{\sin\left(\frac{\pi}{N}k\right)}e^{-j\frac{\pi}{N}(M-1)k}
$$
根据定义，$X[0]=M$，并且如果 $Mk/N$ 是整数，则 $X[k]=0$.
## 3.3 DFS
$$
\tilde{X}(k)=\operatorname{DFS}\{{\tilde{x}}(n)\}=\sum_{n=0}^{N-1} {\tilde{x}}(n) e^{-j\frac{2\pi}{N} nk}=\sum_{n=0}^{N-1} {\tilde{x}}(n)W_{N}^{nk}\\
\tilde{x}(n)=\operatorname{IDFS}\{\tilde{X}(k)\}=\frac{1}{N}\sum_{k=0}^{N-1} \tilde{X}(k) e^{j\frac{2\pi}{N} nk} = \frac{1}{N}\sum_{k=0}^{N-1}\tilde{X}(k) W_{N}^{-nk}
$$
**圆周位移**
$$
\tilde{x}[n-M]R_{N}[n]=x[\operatorname{mod}(n-m,N)]
$$
## 3.4 DFT 性质
- **周期序列的移位**：
$$
\operatorname{DFT}\{x[(n+m)_{N}]\}=W_{N}^{-mk} X(k)=e^{j\frac{2\pi}{N}mk} X(k)
$$
幅度不变，相角位移。
$$
\operatorname{IDFT}\{X[(k+m)_{N}]\}=e^{-j\frac{2\pi}{N}mn} x[n]
$$
- **圆周翻转特性**：
$$
\operatorname{DFT}\{x[(-n)_{N}]\}=X[(-k)_N]\\
\operatorname{DFT}\{x^*[(-n)_N]\}=X^*[(k)_N]
$$
- **圆周共轭对称/反对称序列** 的分解：
- 圆周共轭对称序列：$x_{ep}[n]=x_{ep}^*[(-n)_N]$（全为实数且对称的序列是圆周共轭对称序列）
- 圆周共轭反对称序列：$x_{op}[n]=-x_{op}^*[(-n)_N]$.
$$
x[n]=x_{ep}[n]+x_{op}[n]
$$
$$
\begin{cases}
x_{ep}[n]=\frac{1}{2}(x[n]+x^*[(-n)_N])\\
x_{op}[n]=\frac{1}{2}(x[n]-x^*[(-n)_N])
\end{cases}
$$
对于时域和频域，一方分解为实部+虚部，另一方分解为对称+反对称，互相对应。需要 记忆共轭对称分量的形式和共轭反对称分量的形式。
特别地，如果时域只有实部部分，则对应频域只有对称部分，满足：
$$
X[k]=X^*[(-k)_N]\Rightarrow \begin{cases}
|X(k)|=|X(N-k)|\\
\arg X(k)=-\arg X(N-k)
\end{cases}
$$
利用圆周共轭对称性可以 减少实序列 DFT 的计算量。
例如 **用一次复数序列的 DFT 来求得两个实数序列的 DFT**，我们构造复数序列：
$$
x[n]=x_1[n]+jx_2[n]
$$
其中 $x_{1,2}[n]$ 为实数序列，则共轭对称分量和共轭反对称分量分别为：
$$
X_{ep}[k]=\operatorname{DFT}\{x_1[n]\},\\X_{op}[k]=\operatorname{DFT}\{jx_2[n]\}\Rightarrow \operatorname{DFT}\{x_2[n]\}=\frac{1}{j} X_{op}[k]
$$
**利用 $\boldsymbol N$ 点复序列的 DFT，计算 $\boldsymbol{2N}$ 点实序列 $x[n]$ 的 DFT**：首先，我们构造 $x_1,x_2$.
$$
x[n]=\begin{cases}
x_1[k],&n=2k\\x_2[k],&n=2k+1
\end{cases}
$$
令 $y[n]=x_1[n]+jx_2[n]$ 利用：
$$
\begin{cases}
\operatorname{DFT}\{x_1[n]\}=Y_{ep}[k]=(Y[k]+Y^*[(-k)_N])/2\\
\operatorname{DFT}\{x_2[n]\}=-jY_{op}[k]=-j(Y[k]-Y^*[(-k)_N])/2
\end{cases}
$$
计算得到 $X_1[k]$ 和 $X_2[k]$. 根据 DFT 定义，
$$
\begin{aligned}
X[k]&=\sum_{n\mathrm{~even}} x_1[n] W_{2N}^{nk}+\sum_{n\mathrm{~odd}} x_2[n] W_{2N}^{nk}\\
&=\sum_{n\mathrm{~even}} x_1[n] W_{N}^{\frac{n}{2}k}+W_{2N}^{k}\sum_{n\mathrm{~odd}} x_2[n] W_{N}^{\frac{n-1}{2}k}\\
&=X_1[k]+W_{2N}^k X_2[k],\quad k=0,1,\cdots,N-1
\end{aligned}
$$
$$
X[k+N]=X_1[k]+W_{2N}^{k+N}X_2[k]\\
=X_1[k]-W_{2N}^{k} X_2[k],\quad k =0,1,\cdots,N-1
$$
- **Parseval 定理**：
$$
\sum_{n=0}^{N-1}|x(n)|^2=\frac{1}{N}\sum_{k=0}^{N-1}|X(k)|^2
$$
若 $x(n)$ 为实序列，则
$$
\sum_{n=0}^{N-1}x^2(n)=\frac{1}{N}\sum_{k=0}^{N-1}|X(k)|^2
$$
要点：计算模长。
对于 DTFT 来说有，
$$
\sum_{n=0}^{N-1}|x(n)|^2=\frac{1}{2\pi }\int_{-\pi}^{\pi} |X(e^{j\omega})|^2\mathrm d \omega
$$
- **圆周卷积和** 定义：
$$
y[n]=\sum_{m=0}^{L-1} x_1[m]x_2[(n-m)_L]
$$
$$
Y[k]=X_1[k]X_2[k]
$$
若 $x_1[n]$ 和 $x_2[n]$ 均补值到 $L$ 点，计算 $y[n]=x_1[n]x_2[n]$，可得
$$
Y[k]=\frac{1}{L}X_1[k]*_L X_2[k]
$$
线性卷积和和圆周卷积和的关系：两个有限长序列补零拓展后的线性卷积和以 $L$ 为周期进行延拓后，所得周期序列的主值序列，即为此两序列的 $L$ 点圆周卷积和。
> **例题** 计算 $x(n)=\{3,2,0,2\}$ 和 $h(n)=\{4,-2,1,-1\}$ 的圆周卷积和，可以使用比较简便的方法：
>
> | $x(n)$ | 3 | 2 | 0 | 2 | $y(n)$ |
> | ------------ | ---- | ---- | ---- | ---- | ------ |
> | $h((-n)_4)$ | 4 | -1 | 1 | -2 | 6 |
> | $h((1-n)_4)$ | -2 | 4 | -1 | 1 | 4 |
> | $h((2-n)_4)$ | 1 | -2 | 4 | -1 | -3 |
> | $h((3-n)_4)$ | -1 | 1 | -2 | 4 | 7 |
>
> 可得：
> $$
> y(n)=\{6,4,-3,7\}
> $$
> **例题** 已知有限长序列为
> $$
> x(n)=\delta(n-2)+4\delta(n-4)
> $$
>
> 1. 求其 8 点 DFT；
> $$
> X(k)=\sum_{n=0}^{N-1} x(n)W_{N}^{nk}\\
> =W_{N}^{2k}+4W_{N}^{4k}=(-j)^{k}+4(-1)^{k}
> $$
> 计算 $X(0\sim 7)$.
>
> 2. 若 $h(n)$ 的 8 点 DFT 为 $H(k)=W_{8}^{-3k}X(k)$，求 $h(n)$.
> $$
> H(k)=\sum_{n=0}^{N-1} x(n)W_{N}^{(n-3)k}=\sum_{n=\left\langle N\right\rangle}x((n+3)_N)W_{N}^{nk}\\
> $$
>
> $$
> h(n)=\delta(n-7)+4\delta(n-1)
> $$
>
> 3. 若序列 $y(n)$ 的 8 点 DFT 为 $Y(k)=X(k)H(k)$，求 $y(n)$.
> $$
> y(n)=\delta(n-1)+8\delta(n-3)+16\delta(n-5)
> $$
## 3.5 傅里叶变换的各种可能形式
## 3.6 频域采样定理
给定 $x[n]\in l_2(\Z)$（有限支持/无限序列），计算其 DTFT $X(e^{j\omega})\in L_2(\R)$，表达式为：
$$
X(e^{j\omega})=\sum_{n=-\infin}^{\infin} x[n] e^{-j\omega n}
$$
进行频域采样，采样 $N$ 点：
$$
\tilde{X}[k]=X(e^{j\omega})|_{\omega=2\pi k/N}=\sum_{n=-\infin}^{\infin} x[n] W_{N}^{kn}
$$
进行 IDFS 还原：
$$
\tilde{x}[n]=\frac{1}{N}\sum_{n=-\infin}^{\infin} \tilde{X}[k] W_{N}^{-kn}
$$
关心 $x[n]$ 与 $\tilde{x}[n]$ 的关系。展开可得：
$$
\begin{aligned}\tilde{x}[n]&=\frac{1}{N}\sum_{n=-\infin}^{\infin} \tilde{X}[k]e^{jk\frac{2\pi}{N}n}\\
&=\frac{1}{N}\sum_{n=-\infin}^{\infin}
\left(\sum_{m=-\infin}^\infin x[m]W_N^{km}\right) W^{-kn}_{N}\\
&=\sum_{m=-\infin}^{\infin} x[m] \left(\frac{1}{N}\sum_{k=0}^{N-1}W_{N}^{k(m-n)}\right)
\end{aligned}
$$
因为只有 $m-n$ 是 $N$ 的倍数的时候后面一项等于一，否则等于零，
$$
\tilde{x}[n]=\sum_{r=-\infin}^{\infin}x[n+rN]
$$
研究 $\tilde{x}[n]$ 与 $x[n]$ 的关系：**$\boldsymbol{\tilde{x}[n]}$ 是 $\boldsymbol{x[n]}$ 的周期延拓，延拓周期是 $N$**.
研究周期延拓造成的混叠现象：
1. 当 $x[n]$ 是无限长序列，则延拓过程中一定出现混叠，$\tilde{x}[n]\not=x[n]$. 频域抽样次数 $N$ 越大，失真越小。
2. 当 $x[n]$ 是有限支持序列，有限支持区域长度为 $M$.
- $N\ge M$，周期延拓无混叠，可以由 $\tilde{x}[n]$ 恢复 $x[n]$；
- $N 由此可得，频域抽样产生时域的周期延拓，而时域抽样产生频域的周期延拓。
**频域插值重构**：使用采样点 $X(k)|_{z=e^{j2\pi \frac{k}{N}}}$ 重构 $X(z)$.
$$
\begin{aligned}
X(z)&=\sum_{n=0}^{N-1} x(n)z^{-n}\\
&=\sum_{n=0}^{N-1}\left[\frac{1}{N}\sum_{k=0}^{N-1} X(k)W_{N}^{-nk}\right]z^{-n}\\
&=\frac{1}{N}\sum_{k=0}^{N-1}X(k)\left[\sum_{n=0}^{N-1} W_{N}^{-nk}z^{-n}\right]\\
&=\frac{1}{N}\sum_{k=0}^{N-1} X(k) \frac{1-W_{N}^{-Nk}z^{-N}}{1-W_{N}^{-k} z^{-1}}\\
&=\frac{1-z^{-N}}{N}\sum_{k=0}^{N-1}\frac{X(k)}{1-W_{N}^{-k} z^{-1}}\\
&=\sum_{k=0}^{N-1}X(k)\Phi_k(z)
\end{aligned}
$$
插值函数：
$$
\Phi_{k}(z)=\frac{z^{N}-1}{Nz^{N-1}(z-W_{N}^{-k})}
$$
$$
\Phi(z)|_{z=W_{N}^{-r}}=\delta(r-k)
$$
插值函数零点：$z=W_{N}^{-r},r=0,1,2,\cdots,k-1,k+1,\cdots,N-1$.
代入 $z=e^{j\omega}$ 进入 $\Phi_k(z)$ 可得
$$
\Phi(\omega)=\frac{1}{N}\frac{\sin(\omega N/2)}{\sin(\omega/2)}e^{-j(N-1)\omega/2}
$$
重写 $X(z)$ 表达式为：
$$
\Phi(z)=\sum_{k=0}^{N-1} X(k) \Phi(\omega-2\pi k/N)
$$
## 3.7 非周期连续时间信号谱分析
### 3.7.1 时域采样
由时域采样定理：要求采样频率 $f_s\ge 2f_h$，其中 $f_h$ 是带限信号的最高频率。可以适当增加采样频率，有助于减小后面的混叠失真，取 $f_s=(3\sim 6)f_h$. 如果不是带限信号，需要加入防混叠滤波器。
当抽样频率不符合要求时，会产生 **频谱的混叠失真**。
### 3.7.2 时域截断
可以看成原信号乘以窗函数：
$$
d[n]=\begin{cases}1,&0\le n\le N-1\\
0,& \mathrm{else}.
\end{cases}
$$
如下图，原始信号频谱图由频率为 $100\mathrm{~Hz}$ 和 $120 \mathrm{~Hz}$ 的谱线构成，经过加窗之后，卷积形成下面的频谱图。因为窗函数存在主瓣和旁瓣，且主瓣存在一定宽度，所以对频谱进行了一定程度的展宽，**造成了频谱泄露的现象**。
- 选择不同种类的窗函数，可以增大主旁瓣幅度比，从而减少 **谱间干扰**.
例如选择海明窗函数，旁瓣比主瓣幅度小 $32\mathrm{~dB}$，但是主瓣宽度变成 $8\pi/N$ 增加一倍，又会增加频谱泄露的程度。
- 增加窗长 $N$，可以减小主瓣宽度，从而减少 **频谱泄露** 的程度。
当窗长 $N$ 不是 $x[n]$ 信号周期长度的整数倍时，会产生频谱泄露，反之不存在。
### 3.7.3 周期延拓
时域上的周期延拓，对应频域上的采样。根据频域采样定理，需要采样点数 $M\ge N$，我们取 $M=N$.
设 $N$ 为序列长度，$T$ 为采样周期，则采样的总时间为 $NT=T_0$，可得频率分辨率为：
$$
\boxed{F_0=\frac{1}{T_0}=\frac{1}{NT}=\frac{f_s}{N}}
$$
频率分辨率越小，分辨接近频率信号的能力越强。
提高分辨率的方法：
- 增加有效数据长度 $T_0$. 若此时 $f_s$ 不变，抽样点数增加.
- 用补零点（增加频域抽样点 $M$ 数）的方式不能增加 $N$ 值，不能提高分辨率。
DFT 频谱间隔为 $f_s/N$，得到的是连续频谱的等间隔的 $N$ 点抽样值，而这 $N$ 点抽样值中的任意相邻两点之间的频率点上的频谱值是不知道的，就好像是通过一个栅栏的缝隙观看一个镜像一样，称为 **栅栏效应**。
**减小栅栏效应**
- 在数据长度 $T_0$ 不变的情况下，增加 $f_s$，抽样点数 $N$ 增多；
- 如果 $T_0$ 不变，时域有效抽样点数也不变，则可在有效 $N$ 点数据后补零值，相当于抽样点为 $M>N$；
- 在 $f_s$ 不变的情况下增加 $T_0$，相当于增加 $N$.
### 3.7.4 计算 DFT
### 3.7.5 谱分析综合习题
分析信号：
$$
x(t)=\cos(2\pi f_1 t)+\cos (2\pi f_2 t),f_1=100\mathrm{~Hz},f_2=120\mathrm{~Hz}
$$
用采样频率 $f_s=600\mathrm{~Hz}$ 对其进行采样。
- 检查 $f_s>2f_h=240\mathrm{~Hz}$ 满足奈奎斯特采样条件；
- 频率分辨率为 $f_s/N$，需要保证 $N\ge 30$，才能分辨两条谱线。采样前周期为 $1/20 \mathrm{~s}$，需要保证 $Nf_s$ 为 $1/20$ 的倍数，保证 $N=30k$，才能没有频谱混叠。
- 如果选择的截断窗长度不是 $30$ 的倍数，则会产生频谱混叠效应。
分析信号：
$$
x_a(t)=\cos (2\pi f_1 t)+\frac{1}{2}\cos (2\pi f_2 t)+\frac{1}{2}\cos (2\pi f_3t)
$$
其中 $f_1=600\mathrm{~Hz},f_2=500\mathrm{~Hz},f_3=700\mathrm{~Hz}$.
1. 选择采样周期 $f_s$，第一要求 $f_s>2f_h$ 使得频谱无混叠，第二要求 $f_s$ 为有理数，使得采样后 $x[n]$ 是周期序列；
2. 抽样点数 $N$ 应该满足 $NT_s=N/f_s$ 是原序列周期的整数倍，才能没有频谱泄露。
原序列周期为 $\operatorname{gcd}(1/600,1/500,1/700)=1/100$。假设 $f_s=2100\mathrm{~Hz}$，那么 $N=21k$，才能没有频谱泄露。
3. 假设使用 $f_s=3\mathrm{~kHz}$ 频率抽样，抽样点数 $N$ 为 512 点，因为 $N/f_s$ 不是原始周期的整数倍，所以会产生频谱泄露。
如果要求 $f_s=3\mathrm{~kHz}$ 的情况下，既没有频谱泄露，又能分辨所有频率分量，要求：
$$
F_0=\frac{f_s}{N}\ge 100\mathrm{~Hz}\quad \frac{N}{f_s} 为 1/100整数倍
$$
我们可以取 $N=30$. 恰好可以分辨所有频率分量。
分析序列：
$$
x[n]=\cos [0.48\pi n]+\cos[0.52\pi n]
$$
1. 取 $N=10$，假设抽样频率为 $f_s$，则原始的频率间隔为 $0.02 f_s$，
此时的频率分辨率为：
$$
F_0=\frac{f_s}{N}=0.2 f_s > 0.02 f_s
$$
无法分辨频率分量；
2. 取 $N=10$，但是补 90 个零，因为 $F_0=1/T_0$，$T_0$ 为有效数据的长度没有改变，所以频率分辨率没有改变，但是减少了栅栏效应。
3. 取 $N=100$，因为 $F_0=f_s/100=0.01 f_s<0.02f_s$，所以可以分辨所有频率分量。同时，因为序列周期为 $N'=50$，$N=100$ 是 $50$ 的倍数，所以没有频谱泄露。
分析正弦信号：
$$
x(t)=\cos (2\pi 100 t)+\cos (2\pi 400 t)
$$
采样频率 $f_s=900\mathrm{~Hz}$，采样点数 $N=64$.
1. 得到 $x(n)$ 是否为周期序列？如果是，$x(n)$ 的最小周期为多少？频率分辨率为多少 Hz?
是否会发生频谱混叠？原序列 $f_h=400\mathrm{~Hz}$，满足奈奎斯特条件：
$$
f_s>2f_h
$$
因此不会发生混叠。
采样间隔为 $T_s=1/900 \mathrm{~s}$，则
$$
x(n)=x_a(nT_s)=\cos\left(\frac{2\pi}{9}n\right)+\cos\left(\frac{8\pi}{9}n\right)
$$
$x(n)$ 的最小周期为 $N=9$.
频率分辨率 可以通过下述表达式计算得到：
$$
F_0=\frac{1}{NT_s}=\frac{f_s}{N}=14.0625\mathrm{~Hz}
$$
其中 $NT_s$ 可以理解为有效采样长度的时间。
2. 如果我们想要 $|Y(k)|$ 中得到的实际频率和 $x(t)$ 频率成分一致，能否通过对于 64 点矩形窗截取的 $x(n)$ 进行补零来达成目的，原因是什么？能否通过增加矩形窗的长度来达到目的，原因是什么？
频率响应的峰值点为：
$$
\frac{2\pi}{9},\frac{8\pi}{9}
$$
如果能够使得采样点 $2\pi k/N$ 恰好落在峰值点上，比如取 $N$ 为 9 的倍数，补 $8$ 个零达到 $72$，就可以使得频率成分一致。但是因为此时存在弱信号对强信号的遮盖作用（因为 DTFT 频谱图的采样长度 $N=64$，抽样的点数为 $M=72$，窗函数零点不是一一对应，旁瓣对主瓣产生遮盖作用）
例如，对于 $\cos\left(\frac{2\pi}{9}n\right)+\cos\left(\frac{8\pi}{9}n\right)$，频率成分是一致的。
但是对于 $\cos\left(\frac{7\pi}{36}n\right)+\cos\left(\frac{8\pi}{36}n\right)$，取点 $N=20$，补零到 $M=36$. 取点比较少，频率分辨率较高，且频率之间相差比较小，容易受到旁瓣干扰。
在这种情况下，可以增加窗的长度，提升谱分析的频率分辨率；选择其它旁瓣峰值衰减大的窗函数，减小对弱信号的掩盖
增加矩形窗的长度 $N$，序列 $x(t)$ 的周期为 $\operatorname{gcd}(1/100,1/400)=1/400$，保证 $NT_s=k/100$. 比如我们可以取 $N=72$，就可以使得频率成分一致。
## 3.8 FFT
### 3.8.1 DIT（时间抽取）算法
1. 奇偶分组：
$$
x_1=\{x[0],x[2],x[4],\cdots,x[N-2]\}\\
x_2=\{x[1],x[3],x[5],\cdots,x[N-1]\}
$$
分别计算 DFT $X_1[k],X_2[k]$,
2. 序列 $x$ 的 DFT 可以表示为：
$$
\begin{aligned}
X[k]&=\sum_{n=0}^{N-1}x[n]W_{N}^{nk}\\
&=\sum_{n=0}^{N/2-1}x[2n]W_{N}^{2nk}+\sum_{n=0}^{N/2-1}x[2n+1]W_{N}^{(2n+1)k}\\
&=X_1[k]+W_{N}^{k} X_2[k]
\end{aligned}
$$
前一半和后一半的输出：
$$
\begin{cases}
X[k]=X_1[k]+W_{N}^k X_2[k]\\
X[N/2+k]=X_1[k]-W_{N}^{k} X_2[k]
\end{cases}
$$
3. 基本蝶形运算：
4. 绘制信号流图 $N=8$.
因为是时间抽取，所以 $x(0\sim 7)$ 按二进制倒序排列。然后依次每层运用基本蝶形运算，需要注意每层中因为对应的 $N$ 不同，需要将 $k$ 乘以相应的倍数。
### 3.8.2 DIF（频率抽取）算法
1. 对 DFT 表达式进行变换：
$$
\begin{aligned}
X[k]&=\sum_{n=0}^{N} x(n)W_{N}^{nk}\\
&=\sum_{n=0}^{N/2-1} x(n)W_{N}^{nk}+x(n+N/2)W_{N}^{(n+N/2)k}\\
&=\sum_{n=0}^{N/2-1} \left(x(n)+(-1)^{k} x\left(n+N/2\right)\right)W_{N}^{nk}
\end{aligned}
$$
2. 因为 $X[k]$ 的表达式和 $k$ 的奇偶性相关，所以有必要按照奇偶分组。
当 $k=2r$，代入表达式，得到：
$$
X_1[r]=X[2r]=\operatorname{DFT}\{x(n)+x(n+N/2)\}
$$
当 $k=2r+1$，代入表达式，得到：
$$
X_2[r]=X[2r+1]=\operatorname{DFT}\{(x(n)-x(n+N/2))W_{N}^n\}
$$
3. 基本蝶形运算：
4. 绘制信号流图 $N=8$.
### 3.8.3 运算次数统计
- 运算图层数：$\log_2 N$.
- 每层 $N/2$ 个蝶形运算，蝶形运算总数为 $N/2\log _2 N$.
- 每个蝶形运算对应两个复数加法（减法），总数为 $N\log_2N$.
- 每个蝶形运算对应一个复数乘法，总数为 $N/2\log_2 N$. 如果不算乘以 $\pm1,\pm j$，需要对应减去。
- 总的计算复杂度为 $N\log_2N$.
### 3.8.4 矩阵分解视角
**DIT 算法**
$$
W_8=\begin{pmatrix}
I_4&I_4\\
I_4&-I_4
\end{pmatrix}\begin{pmatrix}
I_4&0_4\\
0_4&\Lambda_4
\end{pmatrix}\begin{pmatrix}
W_4&0_4\\
0_4&W_4
\end{pmatrix}D_8
$$
从蝶形图的角度也可以得到：
**DIF 算法**
$$
W_8=D^\top_8\begin{pmatrix}
W_4&0_4\\
0_4&W_4
\end{pmatrix}\begin{pmatrix}
I_4&0_4\\
0_4&\Lambda_4
\end{pmatrix}\begin{pmatrix}
I_4&I_4\\
I_4&-I_4
\end{pmatrix}
$$
对称阵转置后也相等，证明 DIT 和 DIF 是等价的。
## 3.9 综合题目
以下关于频域取样错误的是
- [ ] 如果频域取样点数大于序列长度则可以通过频域取样重构时域信号；
- [ ] 如果频域取样点数小于序列长度则无法通过频域取样重构时域信号；
- [ ] 当频域取样点数小于序列长度时，也可以通过 DFT 计算频域取样；
- [x] 序列的频域取样如果是实序列，则傅里叶变换一定是实函数。
-------
序列 $x[n]=R_5[n]$，傅里叶变换和 5 点 DFT 分别为 $X(e^{j\omega})$ 和 $X[k]$，则错误的是（）
- [x] $X(e^{j\omega})=e^{-j2.5\omega} A(e^{j\omega})$，其中 $A(e^{j\omega})$ 是实函数；
- [ ] $X[k]=e^{-j4\pi k/5}A[k]$，其中 $A[k]$ 是实序列；
- [ ] $X[k]$ 是实序列；
- [ ] $X[k]=X[(N-k)_N]R_N[n]$.
配对：
$$
W_N^0+W_N^{k}+W_N^{2k}+W_{N}^{3k}+W_{N}^{4k}=W_N^{2k}\cdot R
$$
其中 $R$ 为实数。